package algorithm;

import util.ListNode;

/**
 * Description:
 *  给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
 *  给定一个链表: 1->2->3->4->5, 和 n = 2.
 *  当删除了倒数第二个节点后，链表变为 1->2->3->5.
 *  给定的 n 保证是有效的。
 *  你能尝试使用一趟扫描实现吗？
 * @author: chengrongkai
 * Date: 2021/3/8
 */
public class Solution11 {

    public static void main(String[] args) {
        ListNode node5 = new ListNode(5);
        ListNode node4 = new ListNode(4);
        node4.next = node5;
        ListNode node3 = new ListNode(3);
        node3.next = node4;
        ListNode node2 = new ListNode(2);
        node2.next = node3;
        ListNode node1 = new ListNode(1);
        node1.next = node2;
        int n = 1;
        ListNode solution = solution(node5, n);
        while (solution != null){
            System.out.println(solution.val);
            solution = solution.next;
        }
    }

    /**
     * 定义一个辅助的头部节点pre，pre.next指向node，定义两个节点head和cur指向pre，head开始遍历,当head和cur之间间隔n-1时，cur开始遍历，head遍历到尾部时，
     * cur所在位置即为要删除的节点的上一个节点。
     * @param node
     * @param n
     * @return
     */
    public static ListNode solution(ListNode node,int n){
        ListNode pre = new ListNode(0);
        pre.next = node;
        ListNode head = pre;
        ListNode cur = pre;
        int count = 0;
        while (head.next != null){
            if (count > n-1){
                cur = cur.next;
            }
            head = head.next;
            count++;
        }
        ListNode next = cur.next;
        cur.next = next.next;
        return pre.next;
    }
}
